#include <iostream>
#include <time.h>
#include <Windows.h>
using namespace std;

// 插入排序
template <typename T>
void InsertSort(T *st, T *ed)
{
    int n = ed - st;
    for (int i = 1; i < n; i++)
    {
        for (int j = i; j > 0; j--)
            if (st[j] < st[j - 1])
                swap(st[j], st[j - 1]);
            else
                break;
    }
}

// 快速排序
template <typename T>
void q_sort(T *st, T *ed)
{
    int n = ed - st;
    if (n <= 1)
        return;
    else if (n <= 15)
    {
        InsertSort(st, ed);
        return;
    }
    int l = 0, r = n - 1;
    int midi, mid = l + r >> 1;
    if (st[r] >= st[l])
        midi = st[mid] >= st[r] ? r : (st[mid] >= st[l] ? mid : l);
    else
        midi = st[mid] >= st[l] ? l : (st[mid] >= st[r] ? mid : r);
    if (midi != l)
    {
        st[midi] = st[midi] ^ st[l];
        st[l] = st[midi] ^ st[l];
        st[midi] = st[midi] ^ st[l];
    }
    int prev = 0, cur = 1;
    while (cur < n)
    {
        if (st[cur] <= st[0] && ++prev != cur)
        {
            st[prev] = st[prev] ^ st[cur];
            st[cur] = st[prev] ^ st[cur];
            st[prev] = st[prev] ^ st[cur];
        }
        cur++;
    }
    st[prev] = st[prev] ^ st[0];
    st[0] = st[prev] ^ st[0];
    st[prev] = st[prev] ^ st[0];
    q_sort(st, st + prev);
    q_sort(st + prev + 1, ed);
}

// 希尔排序
template <typename T>
void ShellSort(T *st, T *ed)
{
    int n = ed - st;
    int delt = n;
    while (delt /= 2)
        for (int rt = 0; rt < delt; rt++)
            for (int i = rt + delt; i < n; i += delt)
            {
                for (int j = i; j > rt; j -= delt)
                    if (st[j] < st[j - delt])
                        swap(st[j], st[j - delt]);
                    else
                        break;
            }
}

// 归并排序
template <typename T>
void _MergSort(T *st, T *ed, T *tmp)
{
    int n = ed - st;
    if (n <= 1)
        return;

    int l = 0, r = n - 1, mid = 1 + (l + r >> 1);
    _MergSort(st, st + mid, tmp);
    _MergSort(st + mid, ed, tmp + mid);

    int s1 = l, e1 = mid - 1, s2 = mid, e2 = r, s = l;
    while (s1 <= e1 && s2 <= e2)
    {
        if (st[s1] < st[s2])
            tmp[s++] = st[s1++];
        else
            tmp[s++] = st[s2++];
    }

    while (s1 <= e1)
    {
        tmp[s++] = st[s1++];
    }
    while (s2 <= e2)
    {
        tmp[s++] = st[s2++];
    }

    for (int i = 0; i < n; i++)
        st[i] = tmp[i];
}

template <typename T>
void _CycleMerg(T *st, T *ed, T *tmp)
{
    int gap = 1, n = ed - st;

    while (gap < n)
    {
        for (int i = 0; i < n; i += gap * 2)
        {
            int s1 = i, e1 = s1 + gap - 1, s2 = e1 + 1, e2 = s2 + gap - 1, s = i;
            if (s2 >= n)
                break;
            if (e2 >= n)
                e2 = n - 1;

            while (s1 <= e1 && s2 <= e2)
            {
                if (st[s1] < st[s2])
                    tmp[s++] = st[s1++];
                else
                    tmp[s++] = st[s2++];
            }

            while (s1 <= e1)
            {
                tmp[s++] = st[s1++];
            }
            while (s2 <= e2)
            {
                tmp[s++] = st[s2++];
            }

            for (int j = i; j <= e2; j++)
                st[j] = tmp[j];
        }

        gap *= 2;
    }
}

template <typename T>
void MergSort(T *st, T *ed)
{
    int n = ed - st;
    if (n <= 1)
        return;

    T *tmp = (T *)malloc(sizeof(T) * n);

    // _MergSort(st, ed, tmp);
    _CycleMerg(st, ed, tmp);

    free(tmp);
}

template <typename T>
void CountSort(T *st, T *ed)
{
    T mx = st[0], mn = st[0];
    for (T *p = st; p < ed; p++)
    {
        mx = max(mx, *p);
        mn = min(mn, *p);
    }

    T *tmp = (T *)malloc(sizeof(T) * (mx - mn + 1));

    for (int i = 0; i < mx - mn + 1; i++)
        tmp[i] = 0;

    for (T *p = st; p < ed; p++)
    {
        tmp[*p - mn]++;
    }

    // for (int i = mn; i <= mx; i++)
    //     cout << tmp[i - mn] << ' ';
    // cout << '\n';

    int f = 0;
    for (; st < ed; st++)
    {
        while (!tmp[f])
            f++;
        *st = f + mn;
        tmp[f]--;
    }
}